Multi%2Dview clustering via canonical correlation analysis.
Clustering data in high-dimensions is believed to be a hard problem in general. A number of efficient clustering algorithms developed in recent years address this problem by projecting the data into a lower-dimensional subspace, e.g. via Principal Components Analysis (PCA) or random projections, before clustering. Such techniques typically require stringent requirements on the separation between the cluster means (in order for the algorithm to be be successful). Here, we show how using multiple views of the data can relax these stringent requirements. We use Canonical Correlation Analysis (CCA) to project the data in each view to a lower-dimensional subspace. Under the assumption that conditioned on the cluster label the views are uncorrelated, we show that the separation conditions required for the algorithm to be successful are rather mild (significantly weaker than those of prior results in the literature). We provide results for mixture of The multi-view approach to learning is one in which we have ‘views ’ of the data (sometimes in a rather abstract sense) and, if we understand the underlying relationship between these views, the hope is that this relationship can be used to alleviate the difficulty of a learning problem of interest [BM98, KF07, AZ07]. In this work, we explore how having ‘two views ’ of the data makes
Online Bipartite Perfect Matching With Augmentations.
Abstract—In this paper, we study an online bipartite matching problem, motivated by applications in wireless communication, content delivery, and job scheduling. In our problem, we have a bipartite graph G between n clients and n servers, which represents the servers to which each client can connect. Although the edges of G are unknown at the start, we learn the graph over time, as each client arrives and requests to be matched to a server. As each client arrives, she reveals the servers to which she can connect, and the goal of the algorithm is to maintain a matching between the clients who have arrived and the servers. Assuming that G has a perfect matching which allows all clients to be matched to servers, the goal of the online algorithm is to minimize the switching cost, the total number of times a client needs to switch servers in order to maintain a matching at all times.
What Would Edmonds Do%3F Augmenting Paths and Witnesses for Degree%2DBounded MSTs.
C, degree Bspanning tree, and parameters b, w&gt; 1, produces a tree whose cost is at most wC and whosedegree is at most w w-1 bB + logb n.A primary contribution of K&amp;quot;onemann and Ravi is a Lagrangean relaxation of the BDMST problem. The relaxation in turn gives rise to a problem we call the MDMST problem: to findan MST of minimum degree in a graph. They make central use of a local-search approximation
A parameter%2Dfree hedging algorithm
We study the problem of decision-theoretic online learning (DTOL). Motivated by practical applications, we focus on DTOL when the number of actions is very large. Previous algorithms for learning in this framework have a tunable learning rate parameter, and a barrier to using online-learning in practical applications is that it is not understood how to set this parameter optimally, particularly when the number of actions is large. In this paper, we offer a clean solution by proposing a novel and completely parameter-free algorithm for DTOL. We introduce a new notion of regret, which is more natural for applications with a large number of actions. We show that our algorithm achieves good performance with respect to this new notion of regret; in addition, it also achieves performance close to that of the best bounds achieved by previous algorithms with optimally-tuned parameters, according to previous notions of regret. 1
A parameter%2Dfree hedging algorithm
We study the problem of decision-theoretic online learning (DTOL). Motivated by practical applications, we focus on DTOL when the number of actions is very large. Previous algorithms for learning in this framework have a tunable learning rate parameter, and a barrier to using online-learning in practical applications is that it is not understood how to set this parameter optimally, particularly when the number of actions is large. In this paper, we offer a clean solution by proposing a novel and completely parameter-free algorithm for DTOL. We introduce a new notion of regret, which is more natural for applications with a large number of actions. We show that our algorithm achieves good performance with respect to this new notion of regret; in addition, it also achieves performance close to that of the best bounds achieved by previous algorithms with optimally-tuned parameters, according to previous notions of regret. 1


Privacy constraints in regularized convex optimization

Differentially Private Support Vector Machines

Learning Mixtures of Gaussians using the k%2Dmeans Algorithm

A push%2Drelabel approximation algorithm for approximating the minimum%2Ddegree MST problem and its generalization to matroids.

Beyond Gaussians Spectral Methods for Learning Mixtures of Heavy%2DTailed Distributions.

Finding Metric Structure in Information Theoretic Clustering.
We study the problem of clustering discrete probability distributions with respect to the Kullback-Leibler (KL) divergence. This problem arises naturally in many applications. Our goal is to pick k distributions as “representatives” such that the average or maximum KLdivergence between an input distribution and the closest representative distribution is minimized. Unfortunately, no polynomial-time algorithms with worst-case performance guarantees are known for either of these problems. The analogous problems for l1, l2 and l 2 2 (i.e., k-center, k-median and k-means) have been extensively studied and efficient algorithms with good approximation guarantees are known. However, these algorithms rely crucially on the (geo-)metric properties of these metrics and do not apply to KL-divergence. In this paper, our contribution is to find a “relaxed ” metricstructure for KL-divergence. In doing so, we provide the first polynomial-time algorithm for clustering using KL-divergences with provable guarantees for general inputs. 1
Learning Mixtures of Product Distributions Using Correlations and Independence.
We study the problem of learning mixtures of distributions, a natural formalization of clustering. A mixture of distributions is a collection of distributions D = {D1,...DT}, and � mixing weights, {w1,..., wT} such that i wi = 1. A sample from a mixture is generated by choosing i with probability wi and then choosing a sample from distribution Di. The problem of learning the mixture is that of finding the parameters of the distributions comprising D, given only the ability to sample from the mixture. In this paper, we restrict ourselves to learning mixtures of product distributions. The key to learning the mixtures is to find a few vectors, such that points from different distributions are sharply separated upon projection onto these vectors. Previous techniques use the vectors corresponding to the top few directions of highest variance of the mixture. Unfortunately, these directions may be directions of high noise and not directions along which the distributions are separated. Further, skewed mixing weights amplify the effects of noise, and as a result, previous techniques only work when the separation between the input distributions is large relative to the imbalance in the mixing weights. In this paper, we show an algorithm which successfully learns mixtures of distributions with a separation condition that depends only logarithmically on the skewed mixing weights. In particular, it succeeds for a separation between the centers that is Θ(σ √ T log Λ), where σ is the maximum directional standard deviation of any distribution in the mixture, T is the number of distributions, and Λ is polynomial in T, σ, log n and the imbalance in the mixing
Privacy%2Dpreserving logistic regression.
This paper addresses the important tradeoff between privacy and learnability, when designing algorithms for learning from private databases. We focus on privacy-preserving logistic regression. First we apply an idea of Dwork et al. [7] to design a privacy-preserving logistic regression algorithm. This involves bounding the sensitivity of regularized logistic regression, and perturbing the learned classifier with noise proportional to the sensitivity. We show that for certain data distributions, this algorithm has poor learning generalization, compared with standard regularized logistic regression. We then provide a privacy-preserving regularized logistic regression algorithm based on a new privacy-preserving technique: solving a perturbed optimization problem. We prove that our algorithm preserves privacy in the model due to [7], and we provide learning guarantees. We show that our algorithm performs almost as well as standard regularized logistic regression, in terms of generalization error. Experiments demonstrate improved learning performance of our method, versus the sensitivity method. Our privacy-preserving technique does not depend on the sensitivity of the function, and extends easily to a class of convex loss functions. Our work also reveals an interesting connection between regularization and privacy. 1
A Network Coloring Game.
Abstract. We analyze a network coloring game which was first proposed by Michael Kearns and others in their experimental study of dynamics and behavior in social networks. In each round of the game, each player, as a node in a network G, uses a simple, greedy and selfish strategy by choosing randomly one of the available colors that is different from all colors played by its neighbors in the previous round. We show that the coloring game converges to its Nash equilibrium if the number of colors is at least two more than the maximum degree. Examples are given for which convergence does not happen with one fewer color. We also show that with probability at least 1 − δ, the number of rounds required is O(log(n/δ)). 1
Privacy
Each of two parties PX and P Y holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x; y). That is, PX should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value, f(x; y), and similarly, P Y should not learn any additional information about x.  In this paper we consider two basic questions in the theory of private computations: 1. Which functions can be privately computed ? 2. What is the communication complexity of protocols that privately compute a function  f (in the case that such protocols exist) ? A complete combinatorial characterization of privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1  g(n)  2 \Delta 2  n  there are functions that can be privately...
A rigorous analysis of population stratification with limited data.
Abstract Finding the genetic factors of complex diseases such as can-cer, currently a major effort of the international community, will potentially lead to better treatment of these diseases.One of the major difficulties in these studies, is the fact that the genetic components of an individual not only depend onthe disease, but also on its ethnicity. Therefore, it is crucial to find methods that could reduce the population structureeffects on these studies. This can be formalized as a clustering problem, where the individuals are clustered accordingto their genetic information. Mathematically, we consider the problem of clusteringbit &amp;quot;feature &amp;quot; vectors, where each vector represents the genetic information of an individual. Our model assumes thatthis bit vector is generated according to a prior probability distribution specified by the individual&#039;s membership in apopulation. We present methods that can cluster the vectors while attempting to optimize the number of featuresrequired. The focus of the paper is not on the algorithms, but on showing that optimizing certain objective functionson the data yields the right clustering, under the random generative model. In particular, we prove that some of theprevious formulations for clustering are effective. We consider two different clustering approaches. Thefirst approach forms a graph, and then clusters the data using a connected components algorithm, or a max cut algo-rithm. The second approach tries to estimate simultanously the feature frequencies in each of the populations, and theclassification of vectors into populations. We show that using the first approach \Theta (log N/fl2) data (i.e., total numberof features times number of vectors) is sufficient to find the correct classification, where N is the number of vectors of each population, and fl is the average `22 distance betweenthe feature probability vectors of the two populations. Using the second approach, we show that O(log N/ff4) datais enough, where ff is the average ` 1 distance between thepopulations.
Server Allocation Algorithms for Tiered Systems.

When Random Sampling Preserves Privacy.
Abstract. Many organizations such as the U.S. Census publicly release samples of data that they collect about private citizens. These datasets are first anonymized using various techniques and then a small sample is released so as to enable “do-it-yourself ” calculations. This paper investigates the privacy of the second step of this process: sampling. We observe that rare values – values that occur with low frequency in the table – can be problematic from a privacy perspective. To our knowledge, this is the first work that quantitatively examines the relationship between the number of rare values in a table and the privacy in a released random sample. If we require ɛ-privacy (where the larger ɛ is, the worse the privacy guarantee) with probability at least 1 − δ, we say that 1 a value is rare if it occurs in at most Õ ( ) rows of the table (ignoring log ɛ factors). If there are no rare values, then we establish a direct connection between sample size that is safe to release and privacy. Specifically, if we select each row of the table with probability at most ɛ then the sample is O(ɛ)-private with high probability. In the case that there are t rare values, then the sample is Õ(ɛδ/t)-private with probability at least 1 − δ. 1
A Push%2DRelabel Algorithm for Approximating Degree Bounded MSTs.
Abstract. Given a graph G and degree bound B on its nodes, the bounded-degree minimum spanning tree (BDMST) problem is to find a minimum cost spanning tree among the spanning trees with maximum degree B. This bi-criteria optimization problem generalizes several combinatorial problems, including the Traveling Salesman Path Problem (TSPP). An (α, f(B))-approximation algorithm for the BDMST problem produces a spanning tree that has maximum degree f(B) andcostwithina factor α of the optimal cost. Könemann and Ravi [13,14] give a polynomialtime (1 + 1 β,bB(1 + β)+logbn)-approximation algorithm for any b&gt;1, β&gt;0. In a recent paper [2], Chaudhuri et al. improved these results with a (1, bB+ √ b logb n)-approximation for any b&gt;1. In this paper, we present a(1+ 1, 2B(1 + β)+o(B(1 + β)))-approximation polynomial-time algo-β rithm. That is, we give the first algorithm that approximates both degree and cost to within a constant factor of the optimal. These results generalize to the case of non-uniform degree bounds. The crux of our solution is an approximation algorithm for the related problem of finding a minimum spanning tree (MST) in which the maximum degree of the nodes is minimized, a problem we call the minimumdegree MST (MDMST) problem. Given a graph G for which the degree of the MDMST solution is Δopt, our algorithm obtains in polynomial time an MST of G of degree at most 2Δopt + o(Δopt). This result improves on a previous result of Fischer [4] that finds an MST of G of degree at most bΔopt +logbnfor any b&gt;1, and on the improved quasipolynomial algorithm of [2]. Our algorithm uses the push-relabel framework developed by Goldberg [7] for the maximum flow problem. To our knowledge, this is the first instance of a push-relabel approximation algorithm for an NP-hard problem, and we believe these techniques may have larger impact. We note that for B = 2, our algorithm gives a tree of cost within a (1 + ɛ)-factor of the optimal solution to TSPP and of maximum degree O ( 1 ɛ)for any ɛ&gt;0, even on graphs not satisfying the triangle inequality. 1
On the tandem duplication%2Drandom loss model of genome rearrangement.

What Would Edmonds Do%3F Augmenting Paths and Witnesses for Degree%2DBounded MSTs.
C, degree Bspanning tree, and parameters b, w&gt; 1, produces a tree whose cost is at most wC and whosedegree is at most w w-1 bB + logb n.A primary contribution of K&amp;quot;onemann and Ravi is a Lagrangean relaxation of the BDMST problem. The relaxation in turn gives rise to a problem we call the MDMST problem: to findan MST of minimum degree in a graph. They make central use of a local-search approximation
Server Allocation Algorithms for Tiered Systems.

Deadline scheduling for animation rendering.
We describe a new class of utility-maximization scheduling problem with precedence constraints, the disconnected staged scheduling problem (DSSP). DSSP is a nonpreemptive multiprocessor deadline scheduling problem that arises in several commercially-important applications, including animation rendering, protein analysis, and seismic signal processing. DSSP differs from most previously-studied deadline scheduling problems because the graph of precedence constraints among tasks within jobs is disconnected, with one component per job. Another difference is that in practice we often lack accurate estimates of task execution times, and so purely offline solutions are not possible. However we do know the set of jobs and their precedence constraints up front and therefore some offline planning is possible. Our solution decomposes DSSP into an offline job selection phase
Value%2Dmaximizing deadline scheduling and its application to animation rendering.
We describe a new class of utility-maximization scheduling problem with precedence constraints, the disconnected staged scheduling problem (DSSP). DSSP is a nonpreemptive multiprocessor deadline scheduling problem that arises in several commercially-important applications, including animation rendering, protein analysis, and seismic signal processing. DSSP differs from most previously-studied deadline scheduling problems because the graph of precedence constraints among tasks within jobs is disconnected, with one component per job. Another difference is that in practice we often lack accurate estimates of task execution times, and so purely offline solutions are not possible. However we do know the set of jobs and their precedence constraints up front and therefore some offline planning is possible. Our solution decomposes DSSP into an offline job selection phase
Selfish caching in distributed systems a game%2Dtheoretic analysis.
We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources or cost for access to a remote replica. We show the existence of pure strategy Nash equilibria and investigate the price of anarchy, which is the relative cost of the lack of coordination. The price of anarchy can be high due to undersupply problems, but with certain network topologies it has better bounds. With a payment scheme the game can always implement the social optimum in the best case by giving servers incentive to replicate.
Paths%2C Trees%2C and Minimum Latency Tours.
We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3.59 1-approximation to the minimum latency problem, improving on previous algorithms by a multiplicative factor of 2. Our techniques also give similar improvements for related problems like k-traveling repairmen and its multiple depot variant. We also observe that standard techniques can be used to speed up the previous and this algorithm by a factor of Õ(n). 1
An Extension of Scalable Global IP Anycasting for Load Balancing in the Internet.

